package com.Questions.DP;

import com.Questions.DFS.*;

import java.util.*;

/**
 * 打家劫舍3
 */
public class leetcode337 {
    Map<TreeNode,Integer> f=new HashMap<>();
    Map<TreeNode,Integer> g=new HashMap<>();
    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root,0),g.getOrDefault(root,0));

    }
    // 一遍后序深度优先搜索 一边构造f和g的哈希表
    public void dfs(TreeNode node){
        if(node==null){
            return ;
        }
        dfs(node.left);
        dfs(node.right);
        //f(o)=g(l)+g(r)
        f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
//        g(o)=max(f(l)+g(l))+max(f(r)+g(r))
        g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
    }


    // 可以使用f(o) 表示选择o结点 最大权值之和
    // 可以使用g(o) 表示不选择o结点 最大权值之和

    // 动态规划转移状态转移方程
    // 如果选择o结点 那么他的左右子树都不能选择 f(o)=g(l)+g(r)
    // 如果不选择o结点 那么他的最大权值 之和g(o)=max(f(l)+g(l))+max(f(r)+g(r))

    // 使用哈希表 实现f和g两个动态规划哈希表
    // 对于深搜出的每一个结点求出f和g
    // 最后的结果就是 根节点的f和g的最值


}
